package two.chapter_2.c2_1;

/**
 * 希尔排序
 *       初始h
 *       while(h<N/3){
 *           h=3*h+1;
 *       }
 *       间隔为h的插入排序 ，每次h=h/3;直到h=1
 * @param <Item>
 */
public class ShellSort<Item extends Comparable<Item>> extends Sortable<Item> {

    @Override
    public void sort(Item[] items) {
        int h=1;
        int N=items.length;
        while (h<N/3){
            h=h*3+1;
        }

        while (h>=1){
            for (int i=h;i<N;i++){
                for (int j=i;j>=h && less(items[j],items[j-h]);j-=h){
                    exch(j,j-h,items);
                }
            }
            h=h/3;
        }
    }
}
